// 22. 括号生成
// https://leetcode.cn/problems/generate-parentheses/

/**
示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]
 */

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    const len = n * 2;
    const arr = new Array(len - 1).fill(0).map((_, i) => i);

    let combs = [];

    combination(arr, 0, 1, n, [], combs);
    console.log(JSON.stringify(combs));
    let ret = [];
    combs.forEach((ele) => {
        let arr = new Array(len).fill(')');
        ele.forEach((i) => {
            arr[i] = '(';
        });

        ret.push(arr.join(''));
    });

    console.log(JSON.stringify(ret));
    return ret;
};

function combination(remainArr, headIndex, level, maxLevel, curArr, allArr) {
    // console.log(`curArr is ${JSON.stringify(curArr)}`);
    if (level > maxLevel) {
        allArr.push(curArr);
        return;
    }

    curArr.push(remainArr[headIndex]);

    // 校验当前curArr是否合理
    if (level >= 2) {
        let acc = 0;
        for (let i = curArr.length - 1; i >= 1; i--) {
            acc += curArr[i] - curArr[i - 1] - 1;
        }
        if (acc >= level) return;
    }

    remainArr.splice(0, headIndex + 1);

    if (maxLevel <= curArr.length) {
        allArr.push(curArr);
        return;
    }

    for (let i = 0; i < remainArr.length; i++) {
        combination(
            [].concat(remainArr),
            i,
            level + 1,
            maxLevel,
            [].concat(curArr),
            allArr
        );
    }
}

generateParenthesis(3); // ["((()))","(()())","(())()","()(())","()()()"]
// generateParenthesis(1); // ["()"]
generateParenthesis(6);
